//
//  IPSpaceDistr.java
//
// @author Michael Liljenstam, ISTS, Dartmouth College
//
//  $Id: IPSpaceDistr.java,v 1.3 2003/03/01 21:05:56 mili Exp $

package SSF.App.Worm;

//import java.util.Random;
import com.renesys.raceway.SSF.*;
import SSF.Util.Random.*;
import cern.jet.random.*;
//import java.util.*;

/**
 *  Distribution of announced IP space sizes for ASs.
 *  Empirical distribution for the size of IP space announced by each AS in 
 *  the Internet on Oct 26th, 2001, at 16:48. Based on RIB data from 
 *  University of Oregon's "Route Views" data set.
 *  Also offers a "rough-cut" theoretical distribution to approximate the 
 *  empirical distribution: 
 *  Let X be a sample from N(12.22983, 3.172661). Then the IP space size 
 *  Y = 2^X.
 *  <p>
 *  See main() method for usage example.
 *  </p><p>
 *  Data by BJ Premore, Michael Liljenstam.
 *  </p>
 *  @author Michael Liljenstam, ISTS, Dartmouth College
 */
public class IPSpaceDistr {
  static final int   numVals = 11878;

  static int[] samples={1,12,32,48,64,80,96,128,136,140,144,160,192,256,260,272,276,288,296,320,384,512,520,536,576,636,640,672,704,768,784,796,800,896,928,1024,1032,1040,1056,1088,1152,1280,1296,1328,1344,1408,1536,1537,1540,1568,1664,1792,2048,2080,2304,2336,2432,2560,2624,2688,2816,3072,3328,3456,3584,3840,4096,4352,4416,4608,4864,5120,5376,5632,5888,6144,6272,6400,6656,6912,7104,7168,7424,7680,7936,8192,8208,8340,8448,8704,8720,8960,9216,9472,9728,9984,10240,10496,10752,11008,11264,11520,11776,11808,12032,12056,12160,12288,12544,12560,12800,12864,13056,13312,13568,13824,14080,14336,14592,14848,15104,15232,15360,15616,15872,16128,16384,16448,16640,16656,16896,16912,17152,17408,17536,17664,17680,17920,17936,18176,18432,18688,18944,18960,19200,19456,19712,19744,19968,20224,20480,20736,20992,21248,21504,21760,22016,22032,22272,22528,22784,23040,23296,23552,23808,24064,24320,24576,24832,25088,25344,25600,25856,26112,26368,26624,26880,26896,27136,27648,27904,28160,28416,28672,28928,29184,29440,29696,29952,30208,30464,30480,30720,31232,31488,31744,32000,32256,32512,32768,32800,32896,33024,33280,33536,33792,34048,34304,34560,34816,34961,35072,35328,35344,35584,35840,36352,36608,36864,37120,37376,37632,37888,38144,38912,39168,39424,39696,39783,39936,40192,40448,40556,40704,40960,41216,41472,41728,42240,42496,42752,42764,43008,43264,43520,43776,44032,44288,44800,45056,45312,45568,46080,46336,46848,47104,47360,47616,47872,48128,48384,48640,48736,48896,49152,49408,49664,49920,50688,51200,51456,51712,51840,51968,52224,52480,52736,53248,53504,53760,54272,54528,55040,55296,55552,56064,56320,56832,57088,57344,57600,57856,58112,58368,58624,58880,59136,59648,60160,60672,60928,61184,61440,61696,61952,62208,62720,63744,64000,64768,65024,65280,65536,65664,65792,65800,66048,66176,66304,66432,66560,66816,67072,67328,67584,67840,68096,68352,68608,68864,69120,69376,69632,69888,70144,70400,70656,70912,71168,71424,71680,71936,71944,72448,72704,72960,73216,73728,73984,74240,74496,74752,75008,75264,75520,75776,76032,76288,76800,76848,77312,77568,77824,78080,78336,78592,78848,79360,79616,79872,80128,80640,81152,81408,81920,82176,82432,82688,82944,83200,83456,83712,83968,84224,84480,84496,84736,84992,85248,85504,85760,86016,86272,86528,86784,87296,87808,88320,88832,89088,90112,90368,90624,90880,91136,91392,91904,92416,92928,93184,93440,93696,93952,94208,94464,95232,95488,96768,97024,97280,97296,97536,98048,98304,98560,98816,99072,99328,99840,100096,100352,100608,101888,102144,102400,102656,103168,103424,103680,103936,104192,104704,104960,105472,105728,105984,106496,106752,107008,107264,107520,107776,108032,109568,110336,110848,111616,111872,112384,112640,112896,113152,113408,113664,114688,114944,115200,115456,115712,116224,116992,118528,118784,120064,121600,121856,122112,122624,122880,123136,123392,123904,125952,126464,126720,126976,127488,128000,128256,128768,129024,131072,131328,131584,131840,132096,132352,132608,132864,133120,133152,133376,133408,133632,133888,134144,134400,134720,134912,135168,135424,135680,135936,136192,136448,136960,137216,137728,138112,138496,139264,139776,139808,140288,140800,141056,141312,141568,141824,142080,142336,142592,142848,143360,143616,143872,144640,145408,146432,147456,147712,147968,148224,148992,149248,150528,151040,151552,151808,152320,152576,152832,153344,153600,153856,154112,154624,155648,155904,156160,156416,156672,157440,159488,159744,160000,160512,160528,161024,161280,162304,163584,163840,164096,164352,164608,165632,166144,166400,166656,167936,168704,170496,172032,172288,172544,173312,174336,174592,174848,175360,175616,176384,176896,177152,178944,180224,180480,180736,181248,181504,181760,182272,182784,183040,183296,186880,187648,188160,188416,188928,189184,189440,190208,190464,190720,192512,193024,193280,194304,195072,195584,196608,196864,197120,197632,197888,198144,198400,198656,199168,199680,199936,200192,200704,201472,201728,201984,203264,204544,204800,205056,206080,206848,207104,207616,208896,209408,209920,210688,212736,212992,214272,215808,216064,216320,217088,218112,218880,219136,220160,221440,221952,222208,224768,225024,225792,229376,229888,230144,230912,231168,232192,232448,233472,235520,236800,237568,238336,239104,239760,239872,241408,241920,242944,243968,246784,247040,248576,249856,253952,254976,255744,256000,257024,257536,258304,258560,259840,262144,262400,262656,263168,263680,264192,264228,264704,264960,265472,266240,266752,267264,267520,269568,270336,270848,272384,274688,274944,275456,277504,278528,278784,280064,280832,282112,282624,283136,284928,284992,285184,285440,287232,287744,289280,289792,291072,293376,294912,295424,296448,296704,298240,299776,300544,303360,304128,304640,304896,305152,305920,306944,308992,314880,315392,317696,317952,319232,319488,320256,327680,327936,328192,328448,328960,329216,330240,330496,331264,331520,332288,333328,335104,336128,336896,337408,338432,339200,339456,339968,343808,344064,349952,351744,352256,352512,354304,356608,357632,358400,360704,362752,363008,364544,366080,368640,373248,374016,375040,375552,377344,379392,382720,385536,387072,390144,391424,392448,393216,393728,393984,394496,394752,396288,396800,400384,401408,402688,404480,404992,405760,407552,412416,413696,416768,418048,419840,424704,425984,427520,434176,445696,445952,446976,448000,450048,452096,452608,456192,458752,459776,460544,461056,461312,462848,464384,466944,473344,474368,474624,475136,475904,476160,478464,480256,482816,483840,484096,484352,485888,487168,488704,490496,491520,502272,505600,507904,509440,509696,512256,512768,515584,516864,521472,524288,525056,525824,526080,527872,528384,529920,537600,537856,538112,541440,545024,552704,555008,557312,569856,581632,582656,590080,590592,591364,592896,595712,598528,600064,602112,603904,606208,610048,612608,614656,625408,626048,639232,648960,652288,656384,660480,666112,668416,675072,676608,677376,679168,681216,702976,710656,711936,712960,717824,734720,734976,741376,742400,749056,749312,753664,761600,773888,775168,776448,777984,779520,783616,784384,786432,791296,800000,803584,810240,819968,826624,829184,861952,868352,875776,876544,881920,884736,890368,891392,891648,912896,918528,927744,931072,934144,938496,944384,953088,954368,955648,973568,1001216,1014272,1033216,1033728,1038592,1047040,1048576,1049088,1050368,1055488,1056768,1058304,1071360,1081600,1086208,1087232,1091328,1098752,1099776,1109760,1112064,1113088,1114880,1116416,1117440,1118208,1123072,1128960,1138688,1146880,1152256,1179648,1181952,1207552,1228032,1229824,1240832,1247488,1248768,1250560,1253888,1259010,1261312,1274656,1286144,1286656,1323520,1326080,1346048,1366272,1401344,1424128,1442048,1466112,1469040,1472768,1473536,1515776,1551360,1555968,1604352,1607680,1628160,1629696,1683456,1684992,1707776,1740032,1806336,1811200,1819904,1831168,1904640,1953280,1983232,2043904,2047744,2066176,2073856,2114848,2160128,2170624,2180096,2228480,2243584,2270976,2286848,2303232,2332416,2372096,2405120,2462464,2606848,2607104,2616832,2736384,2742272,2756352,2811392,2816788,2885120,2963712,3054336,3177472,3276800,3293120,3556608,3784448,3795200,3817728,3920640,3957504,4045824,4366336,4561152,4624640,4920320,5098752,5673776,5744384,5967104,6046208,7451904,7498752,7562496,7695616,7740416,7943936,8799488,9255424,9479936,12754432,16246528,16777216,16777984,16778496,16793600,16842752,16859648,16904448,16933888,17437184,17832960,19341568,20043520,20256256,30161664,34328344,36456192,73838848};
    static int[] indexes={0,1,2,9,10,14,16,17,22,23,24,25,26,27,1810,1812,1813,1814,1816,1817,1823,1830,2876,2877,2878,2880,2881,2884,2885,2886,3259,3260,3261,3262,3264,3265,3841,3842,3843,3844,3845,3846,4103,4104,4105,4106,4107,4296,4297,4298,4299,4300,4409,4698,4699,4823,4825,4827,4942,4944,4945,5011,5100,5157,5158,5225,5274,6049,6145,6146,6221,6264,6319,6359,6391,6425,6498,6499,6534,6564,6589,6590,6628,6641,6661,6678,7767,7769,7770,7903,7973,7974,8004,8052,8074,8099,8118,8151,8164,8184,8196,8216,8229,8245,8246,8254,8255,8256,8339,8371,8372,8402,8403,8417,8431,8441,8456,8461,8471,8480,8490,8501,8502,8511,8520,8527,8535,8739,8740,8769,8770,8793,8794,8802,8824,8825,8835,8836,8837,8838,8844,8857,8866,8869,8870,8876,8886,8889,8890,8896,8899,8934,8953,8961,8971,8980,8985,8990,8991,8995,9002,9011,9016,9021,9025,9029,9032,9033,9125,9136,9148,9155,9162,9169,9174,9177,9184,9190,9191,9196,9201,9205,9207,9213,9228,9231,9233,9237,9241,9243,9246,9251,9252,9255,9259,9262,9265,9267,9268,9269,9335,9336,9337,9355,9366,9369,9374,9381,9386,9393,9400,9401,9407,9409,9410,9414,9417,9419,9420,9426,9429,9431,9436,9438,9441,9443,9448,9449,9450,9451,9458,9460,9461,9462,9464,9496,9505,9511,9514,9520,9525,9526,9527,9529,9533,9534,9536,9537,9539,9541,9545,9547,9549,9550,9551,9553,9555,9556,9558,9561,9562,9563,9564,9565,9568,9592,9600,9603,9605,9606,9607,9610,9611,9612,9613,9614,9615,9616,9621,9623,9625,9626,9629,9631,9632,9635,9636,9638,9639,9640,9653,9658,9660,9665,9666,9667,9668,9669,9672,9673,9674,9675,9676,9677,9679,9682,9683,9685,9687,9688,9689,9692,9693,10245,10246,10349,10350,10398,10399,10423,10424,10449,10469,10477,10480,10500,10507,10521,10523,10530,10533,10534,10540,10562,10570,10573,10574,10577,10579,10581,10582,10586,10589,10590,10591,10595,10597,10601,10637,10643,10652,10653,10660,10662,10666,10668,10674,10677,10678,10680,10681,10682,10685,10689,10693,10694,10695,10696,10697,10698,10701,10702,10705,10706,10707,10731,10734,10741,10745,10750,10752,10754,10755,10756,10758,10759,10760,10762,10768,10770,10773,10775,10778,10779,10781,10784,10785,10787,10790,10792,10794,10802,10806,10809,10810,10812,10814,10815,10816,10817,10819,10820,10822,10823,10826,10828,10829,10831,10832,10833,10835,10836,10838,10839,10852,10857,10859,10860,10862,10864,10867,10868,10869,10870,10871,10874,10875,10878,10881,10883,10884,10885,10887,10888,10889,10890,10892,10901,10904,10905,10906,10910,10912,10915,10916,10917,10918,10919,10920,10921,10922,10923,10924,10925,10926,10929,10932,10933,10936,10938,10939,10940,10942,10943,10945,10946,10947,10948,10949,10950,10951,10952,10953,10954,10955,10956,10957,10959,10962,10963,10965,10966,11021,11042,11056,11067,11072,11079,11084,11085,11086,11087,11090,11091,11092,11095,11098,11099,11100,11101,11103,11106,11107,11108,11110,11111,11115,11118,11119,11120,11124,11133,11136,11137,11139,11140,11144,11145,11146,11147,11148,11150,11151,11152,11153,11154,11155,11156,11158,11159,11166,11167,11168,11169,11170,11171,11172,11173,11174,11176,11177,11178,11180,11181,11182,11183,11184,11185,11189,11190,11191,11192,11194,11195,11196,11197,11198,11199,11200,11201,11202,11203,11204,11206,11207,11210,11211,11212,11214,11215,11216,11217,11218,11219,11221,11223,11225,11226,11227,11228,11229,11230,11231,11232,11233,11235,11236,11239,11241,11242,11243,11245,11246,11247,11248,11250,11251,11253,11254,11255,11256,11257,11258,11259,11260,11261,11262,11263,11265,11266,11267,11268,11269,11287,11296,11300,11304,11309,11314,11316,11317,11318,11320,11321,11322,11323,11324,11327,11328,11329,11331,11333,11334,11336,11337,11338,11339,11341,11342,11343,11344,11345,11350,11351,11353,11354,11355,11357,11358,11359,11360,11361,11362,11363,11364,11365,11366,11367,11370,11371,11372,11373,11375,11376,11377,11378,11379,11380,11382,11383,11384,11385,11387,11388,11389,11390,11391,11392,11393,11394,11395,11398,11399,11400,11401,11402,11403,11404,11405,11406,11413,11419,11421,11422,11423,11424,11425,11426,11427,11428,11429,11430,11431,11432,11433,11435,11436,11437,11438,11439,11440,11441,11444,11445,11446,11447,11448,11449,11450,11451,11452,11453,11454,11455,11457,11458,11459,11460,11461,11462,11464,11465,11466,11467,11468,11469,11470,11471,11472,11473,11474,11475,11476,11477,11478,11479,11480,11481,11482,11483,11484,11489,11491,11494,11496,11497,11499,11500,11501,11502,11503,11505,11506,11508,11512,11514,11515,11516,11517,11518,11519,11520,11521,11522,11523,11524,11525,11526,11527,11528,11529,11530,11531,11532,11533,11534,11535,11536,11537,11539,11540,11541,11542,11543,11544,11545,11546,11547,11548,11552,11553,11554,11557,11558,11559,11560,11561,11562,11563,11564,11565,11566,11567,11568,11569,11570,11571,11572,11573,11574,11575,11577,11578,11579,11580,11581,11582,11583,11584,11585,11587,11588,11589,11590,11591,11592,11593,11594,11595,11596,11597,11598,11599,11600,11601,11602,11603,11604,11605,11606,11607,11608,11609,11610,11611,11612,11613,11614,11615,11616,11617,11618,11619,11620,11622,11624,11625,11627,11628,11629,11630,11631,11632,11633,11634,11635,11636,11637,11638,11639,11640,11641,11642,11643,11644,11645,11646,11647,11648,11649,11650,11651,11652,11653,11654,11655,11656,11657,11658,11659,11660,11662,11663,11664,11665,11666,11667,11668,11669,11671,11672,11673,11674,11675,11676,11677,11678,11679,11680,11681,11682,11683,11684,11685,11686,11687,11688,11689,11690,11691,11692,11693,11695,11696,11697,11698,11700,11701,11702,11703,11705,11706,11707,11708,11709,11710,11711,11712,11714,11715,11716,11717,11718,11719,11720,11721,11722,11723,11724,11725,11726,11727,11728,11729,11731,11732,11733,11734,11736,11737,11738,11739,11740,11741,11742,11743,11744,11745,11746,11747,11748,11749,11750,11751,11752,11753,11754,11755,11756,11757,11758,11759,11760,11761,11762,11763,11764,11765,11766,11767,11768,11769,11770,11771,11772,11773,11774,11775,11776,11777,11778,11779,11780,11781,11782,11783,11784,11785,11786,11787,11788,11789,11790,11791,11792,11793,11794,11795,11796,11797,11798,11799,11800,11801,11802,11803,11804,11805,11806,11807,11808,11809,11810,11811,11812,11813,11814,11815,11816,11817,11818,11819,11820,11821,11822,11823,11824,11825,11826,11827,11828,11829,11830,11831,11832,11833,11834,11835,11836,11837,11838,11839,11840,11841,11842,11843,11844,11845,11846,11847,11848,11849,11850,11851,11852,11853,11854,11855,11856,11857,11858,11860,11862,11863,11864,11866,11867,11868,11869,11870,11871,11872,11873,11874,11875,11876,11877};

  static int[] lookup;

  static final double logMean = 12.22983;
  static final double logStdDev = 3.172661;

  static RandomStream rng;
  static Normal       theorDistr;


  /**
   * Initialize the lookup table. Must be called before any samples can be 
   * drawn.
   * @param useTheoreticalDistr Set to <b>true</b> to use the approximate 
   *        theoretical distribution instead of the empirical distr.
   * @param _rng A random number stream. As defined in the SSF.Util.Random
   *            package.
   */
  public static void init(boolean useTheoreticalDistr,
			  RandomStream _rng) {
    // set up RNG
    rng = _rng;

    if (!useTheoreticalDistr) {
      // set up empirical distribution lookup table
      lookup = new int[numVals];
      int cnt = 0;
      for (int i=0; i<indexes.length-1; i++) {
	while (cnt < indexes[i+1]) {
	  lookup[cnt++] = i;
	}
      }
      lookup[cnt] = indexes.length-1;
    } else {
      // set up theoretical distribution
      theorDistr = new Normal(logMean, logStdDev, rng);
    }
  }

  /**
   * @deprecated
   * Draw a sample from the IP space distribution. 
   * @param rnd A random sample U[0,1)
   * @returns A sample for the distribution of AS IP space sizes
   */
    public static long getSample(double rnd) {
    return samples[lookup[(int) (Math.floor(rnd * numVals))]];
  }

  /**
   * Draw a sample from the IP space distribution.
   * @returns The size of the IP space "chunk" allocated to one AS.
   */
  public static long nextLong() {
    if (lookup != null) {
      // use empirical distribution
      return samples[lookup[(int) (Math.floor(rng.nextDouble() * numVals))]];
    } else {
      // use theoretical distribution
      return (long) Math.ceil(Math.pow(2, theorDistr.nextDouble()));
      // round up to avoid sampling size 0
    }
  }

  /**
   * Deallocate the lookup table to let the memory be reclaimed. 
   * No more samples can be drawn from the distribution.
   */
  public static void discard() {
    lookup = null;
  }

  /**
   * Unit test code.
   *
   */
  public static class TestFixture extends Entity {
    RandomStream rng;
    final String RNG_TYPE = "MersenneTwister";
    final String seed = "DefaultSeed";

    public TestFixture(boolean useTheor) {
      // RNG
      try {
	rng = RandomStream.getStream(this,
				     RNG_TYPE,
				     seed);
      } catch (RandomStream.StreamException rngex) {
	  rngex.printStackTrace();
	  System.exit(-1);
      }

      IPSpaceDistr.init(useTheor, rng);
    }

    public void doTest() {
      for (int i=0; i<numVals; i++) {
	System.out.println(IPSpaceDistr.nextLong());
      }
    }
  }

  /**
   * Test code.
   * For normal usage, <i>do not</i> instantiate. Singleton class.
   */
  public IPSpaceDistr(boolean useTheor) {
    TestFixture f = new TestFixture(useTheor);
    
    f.doTest(); // prints out a bunch of samples that can be statistically 
		// tested.
  }
  

  /**
   * Simple test code.
   */
  public static void main(String[] argv) {

    boolean useTheor = false;

    if (argv.length > 0) {
      if (argv[0].compareTo("-theor") == 0) {
	useTheor = true;
      }
    }

    // instantiate just so that the test-fixture can be instatiated
    IPSpaceDistr isd = new IPSpaceDistr(useTheor); 
  }
}
